package main;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Stack;

/**
 * represents a board with history
 * 
 * @author Phil
 * 
 */
public class SympleBoard {

	private static final int GROUP_PENALTY = 6;

	public static final char[] coordinates = { 'A', 'B', 'C', 'D', 'E', 'F',
			'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O' };

	public static final int BOARD_SIZE = 15;

	private static final byte MOVE_EXPAND_WHITE = 100;
	private static final byte MOVE_EXPLORE_WHITE = 101;
	private static final byte MOVE_EXPAND_BLACK = 102;
	private static final byte MOVE_EXPLORE_BLACK = 103;
	private static final byte MOVE_SPECIAL_BLACK = 104;

	public static final byte WHITE = (byte) 0;
	public static final byte BLACK = (byte) 1;

	byte[][] board = new byte[BOARD_SIZE][BOARD_SIZE];
	/** how many groups were created? */
	byte[] groupsCreated = new byte[2];
	/** starting stone for each group */
	HashMap<Byte, Integer> groupStone = new HashMap<Byte, Integer>();
	/** how many groups are actually there? */
	byte[] groupsPresent = new byte[2];

	/** how many stones are there? */
	short[] stones = new short[2];

	HashMap<Byte, Byte> connected = new HashMap<Byte, Byte>();
	// history
	private Stack<Byte> history = new Stack<Byte>();
	// contains all explores
	private Stack<Integer> hist_explores = new Stack<Integer>();
	// contains all expands
	private Stack<LinkedList<Integer>> hist_expands = new Stack<LinkedList<Integer>>();
	// contains the groups connected, corresponding to expands
	private Stack<LinkedList<Byte>> hist_connects = new Stack<LinkedList<Byte>>();

	public boolean move(byte player, int move) {
		if (checkValidMove(player, move)) {
			groupsCreated[player]++;
			groupsPresent[player]++;
			stones[player]++;
			byte group = (byte) (2 * groupsCreated[player] + player);
			groupStone.put(group, move);
			board[move % BOARD_SIZE][move / BOARD_SIZE] = group;
			if (player == WHITE) {
				history.push(MOVE_EXPLORE_WHITE);
			} else {
				history.push(MOVE_EXPLORE_BLACK);
			}
			hist_explores.push(move);
			return true;
		}
		return false;
	}

	@SuppressWarnings("unchecked")
	public boolean move(byte player, LinkedList<Integer> moves) {
		if (checkValidMove(player, moves)) {
			LinkedList<Byte> newConnects = new LinkedList<Byte>();
			for (int move : moves) {
				expand(player, move, newConnects);
			}
			stones[player]++;
			if (player == WHITE) {
				history.push(MOVE_EXPAND_WHITE);
			} else {
				history.push(MOVE_EXPAND_BLACK);
			}
			hist_expands.push((LinkedList<Integer>) moves.clone());
			hist_connects.push(newConnects);
			return true;
		}
		return false;
	}

	public int score(byte player) {
		return stones[player] - GROUP_PENALTY * groupsPresent[player];
	}

	private void expand(byte player, int move, LinkedList<Byte> newConnects) {
		int x = move % BOARD_SIZE;
		int y = move / BOARD_SIZE;

		HashSet<Byte> neighbours = getNeighbours(player, move);
		for (byte neighbour : neighbours) {
			if (board[x][y] == 0) {
				board[x][y] = neighbour;
			} else {
				connect(board[x][y], neighbour, newConnects);
				board[x][y] = (byte) Math.min(board[x][y], neighbour);
			}
		}
	}

	private void connect(byte group1, byte group2, LinkedList<Byte> newConnects) {
		groupsPresent[group1 % 2]--;
		group1 = trace(group1);
		group2 = trace(group2);
		if (group1 < group2) {
			connected.put(group2, group1);
			newConnects.add(group2);
		} else {
			connected.put(group1, group2);
			newConnects.add(group1);
		}
	}

	private byte trace(byte group) {
		while (connected.containsKey(group)) {
			group = connected.get(group);
		}
		return group;
	}

	public void revertMove() {
		byte type = history.pop();
		if (type == MOVE_EXPLORE_WHITE) {
			revertExplore(WHITE);
		} else if (type == MOVE_EXPLORE_BLACK) {
			revertExplore(BLACK);
		} else if (type == MOVE_EXPAND_WHITE) {
			revertExpand(WHITE);
		} else if (type == MOVE_EXPAND_WHITE) {
			revertExpand(BLACK);
		}
	}

	private void revertExplore(byte player) {
		int move = hist_explores.pop();
		board[move % BOARD_SIZE][move / BOARD_SIZE] = 0;
		stones[player]--;
		byte group = (byte) (2 * groupsCreated[player] + player);
		groupStone.remove(group);
		groupsPresent[player]--;
		groupsCreated[player]--;
	}

	private void revertExpand(byte player) {
		LinkedList<Integer> moves = hist_expands.pop();
		for (int move : moves) {
			stones[player]--;
			board[move % BOARD_SIZE][move / BOARD_SIZE] = 0;
		}
		LinkedList<Byte> newConnected = hist_connects.pop();
		for (byte group : newConnected) {
			connected.remove(group);
			groupsPresent[player]++;
		}
	}

	/**
	 * just counts how many adjacent crossings are filled with stones of a given
	 * player, ignored whether they are from the same group
	 * 
	 * @param player
	 * @param pos
	 * @return
	 */
	public int getNeighbourCount(byte player, int pos) {
		int x = pos % BOARD_SIZE;
		int y = pos / BOARD_SIZE;
		int count = 0;
		if (x > 0) {
			if (board[x - 1][y] != 0 && board[x - 1][y] % 2 == player) {
				count++;
			}
		}
		if (x < BOARD_SIZE - 1) {
			if (board[x + 1][y] != 0 && board[x + 1][y] % 2 == player) {
				count++;
			}
		}
		if (y > 0) {
			if (board[x][y - 1] != 0 && board[x][y - 1] % 2 == player) {
				count++;
			}
		}

		if (y < BOARD_SIZE - 1) {
			if (board[x][y + 1] != 0 && board[x][y + 1] % 2 == player) {
				count++;
			}
		}
		return count;
	}

	public boolean checkValidMove(byte player, int move) {
		int x = move % BOARD_SIZE;
		int y = move / BOARD_SIZE;
		if (board[x][y] != 0) {
			return false;
		}
		if (getNeighbourCount(player, move) == 0) {
			return true;
		}
		return false;
	}

	/**
	 * creates a list of all neighbouring groups of the given player (traced
	 * down to their actual index)
	 * 
	 * @param player
	 * @param move
	 * @return
	 */
	private HashSet<Byte> getNeighbours(byte player, int move) {
		HashSet<Byte> neighbours = new HashSet<Byte>();
		int x = move % BOARD_SIZE;
		int y = move / BOARD_SIZE;
		if (x > 0) {
			if (board[x - 1][y] != 0 && board[x - 1][y] % 2 == player) {
				neighbours.add(trace(board[x - 1][y]));
			}
		}
		if (x < BOARD_SIZE - 1) {
			if (board[x + 1][y] != 0 && board[x + 1][y] % 2 == player) {
				neighbours.add(trace(board[x + 1][y]));
			}
		}
		if (y > 0) {
			if (board[x][y - 1] != 0 && board[x][y - 1] % 2 == player) {
				neighbours.add(trace(board[x][y - 1]));
			}
		}
		if (y < BOARD_SIZE - 1) {
			if (board[x][y + 1] != 0 && board[x][y + 1] % 2 == player) {
				neighbours.add(trace(board[x][y + 1]));
			}
		}
		return neighbours;
	}

	public boolean checkValidMove(byte player, LinkedList<Integer> moves) {
		HashSet<Byte> groupsDone = new HashSet<Byte>();
		for (int move : moves) {
			int x = move % BOARD_SIZE;
			int y = move / BOARD_SIZE;
			if (board[x][y] != 0) {
				return false;
			}
			HashSet<Byte> neighbours = getNeighbours(player, move);
			for (byte neighbour : neighbours) {
				if (groupsDone.contains(neighbour)) {
					return false;
				}
				groupsDone.add(neighbour);
			}
		}
		if (groupsDone.size() != groupsPresent[player]) {
			return false;
		}
		return true;
	}
	
	public LinkedList<Integer> getGroupFreePlaces(byte group) {
		return getFreePlaces(groupStone.get(group));
	}

	public LinkedList<Integer> getFreePlaces(Integer pos) {
		int x = pos % BOARD_SIZE;
		int y = pos / BOARD_SIZE;
		LinkedList<Integer> results = new LinkedList<Integer>();

		if (board[x][y] == 0) {
			return results;
		}
		boolean[][] done = new boolean[BOARD_SIZE][BOARD_SIZE];

		floodfill(x, y, done, results);

		return results;
	}

	private void floodfill(int x, int y, boolean[][] done,
			LinkedList<Integer> results) {
		done[x][y] = true;
		if (x > 0) {
			if (!done[x - 1][y] && board[x - 1][y] == 0) {
				done[x - 1][y] = true;
				results.add(y * BOARD_SIZE + (x - 1));
			} else if (!done[x - 1][y] && board[x][y] % 2 == board[x - 1][y] % 2) {
				floodfill(x - 1, y, done, results);
			}
		}
		if (x + 1 < BOARD_SIZE) {
			if (!done[x + 1][y] && board[x + 1][y] == 0) {
				done[x + 1][y] = true;
				results.add(y * BOARD_SIZE + (x + 1));
			} else if (!done[x + 1][y] && board[x][y] % 2 == board[x + 1][y] % 2) {
				floodfill(x + 1, y, done, results);
			}
		}
		if (y > 0) {
			if (!done[x][y - 1] && board[x][y - 1] == 0) {
				done[x][y - 1] = true;
				results.add((y - 1) * BOARD_SIZE + x);
			} else if (!done[x][y - 1] && board[x][y] % 2 == board[x][y - 1] % 2) {
				floodfill(x, y - 1, done, results);
			}
		}
		if (y + 1 < BOARD_SIZE) {
			if (!done[x][y + 1] && board[x][y + 1] == 0) {
				done[x][y + 1] = true;
				results.add((y + 1) * BOARD_SIZE + x);
			} else if (!done[x][y + 1] && board[x][y] % 2 == board[x][y + 1] % 2) {
				floodfill(x, y + 1, done, results);
			}
		}
	}

	@Override
	public String toString() {
		String s = "Symple Board:\n";
		for (int y = 0; y < BOARD_SIZE; y++) {
			s += (15 - y) + ":\t";
			for (int x = 0; x < BOARD_SIZE; x++) {
				s += board[x][y] + "\t";
			}
			s += "\n";
		}
		s += "\t";
		for (int i = 0; i < BOARD_SIZE; i++) {
			s += coordinates[i] + "\t";
		}
		s += "\n\n";
		s += "White groups created: " + groupsCreated[0] + "\n";
		s += "Black groups created: " + groupsCreated[1] + "\n";
		s += "At the points:" + groupStone + "\n";
		s += "White groups present: " + groupsPresent[0] + "\n";
		s += "Black groups present: " + groupsPresent[1] + "\n";
		s += "White stones: " + stones[0] + "\n";
		s += "Black stones: " + stones[1] + "\n";
		s += "Score: " + score(WHITE) + ":" + score(BLACK) + "\n";
		s += "Connected: " + connected.toString();
		return s;
	}
}
